#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: all_path.py 
@version:
@time: 2024/01/25

最终要返回的是一个列表，列表中的元素类型是字符串，每次字符串表示从根节点到一个叶子节点的路径。

从这一点可以判断出，先定义res列表为最终的返回结果，在每一次路径上，如果该节点不是叶子节点，则需要不断向字符串str_中添加元素，

并且在此字符串的基础之上分别递归访问该节点的左右子节点，直到遇到叶子节点时，将该字符串加入res列表中
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
node1.left = node2
node1.right = node3
node2.left = node4
node3.left = node5
node3.right = node6


def all_path(root):
    res = []
    str_ = ""
    dfs(root, res, str_)
    return res


def dfs(root, res, str_):
    if not root:
        return
    else:
        str_ = str_ + str(root.val)
        dfs(root.left, res, str_ + '-')
        dfs(root.right, res, str_ + '-')
    if not root.left and not root.right:
        res.append(str_)


print(all_path(node1))
